package problem42;


//42.接雨水
//https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-100-liked
// 动态规划

class Solution2 {
    public int trap(int[] height) {
        int n = height.length;

        //求出数组的最大值
        int max = 0, maxIndex = 0;
        for(int i = 0; i<n; i++) {
            if(height[i] > max) {
                max = height[i];
                maxIndex = i;
            }
        }

        int[] dp = new int[n];
        dp[maxIndex] = max;
        dp[0] = height[0];
        dp[n-1] = height[n-1];

        for(int i = 1; i<maxIndex; i++) {
            dp[i] = Math.max(dp[i-1], height[i]);
        }
        for(int i = n-2; i>maxIndex; i--) {
            dp[i] = Math.max(dp[i+1], height[i]);
        }

        int sum = 0;
        for(int i = 0; i<n; i++) {
            sum += dp[i]-height[i];
        }
        return sum;
    }
}